#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

		set<vector<int> > result;
		if(num.empty())
			return vector<vector<int> >();

		sort(num.begin(),num.end());
		vector<bool> counts(num.size(),false);

		solve(num,result,0,0,counts,target);

		return vector<vector<int> >(result.begin(),result.end());
    }
private:
	void solve(const vector<int>& cands, set<vector<int> >& result, size_t index,int sum, vector<bool>& counts,int target){
		if(sum > target)
			return;

		if(sum == target){
			vector<int> r;
			for(size_t i=0;i<index;i++){
				if(counts[i]){
					r.push_back(cands[i]);
				}
			}
			result.insert(r);
			return;
		}

		if(index >= cands.size())
			return;

		counts[index] = true;
		solve(cands,result,index+1,sum + cands[index],counts,target);

		counts[index] = false;
		solve(cands,result,index+1,sum,counts,target);
		
	}
};

#endif